// https://leetcode.cn/problems/multiply-strings/

/*
给定两个以字符串形式表示的非负整数 num1 和 num2，返回 num1 和 num2 的乘积，它们的乘积也表示为字符串形式。

注意：不能使用任何内置的 BigInteger 库或直接将输入转换为整数。

*/
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>

using namespace std;

class Solution {
public:
    string multiply(string num1, string num2) {
		if(num1 == "0" || num2 == "0"){
            return "0";
        }
		int len1 = num1.size();
		int len2 = num2.size();
		int maxLen, minLen;
		vector<string> res(maxLen);
		string maxStr;
		string minStr;
		
		if(len1 > len2){
			maxStr = num1;
			minStr = num2;
			maxLen = len1;
			minLen = len2;
		}
		else{
			maxStr = num2;
			minStr = num1;
			maxLen = len2;
			minLen = len1;
		}
		int level = 0; // 当前乘数的位数
		int flag = 0; // 进位标志
		for(int i = minLen - 1; i >= 0; i--){
			string sum = "";
			int k = 0;
			while(k < level){
				sum += '0';
				k++;
			}
			level++;
			int y = minStr[i] - '0';
			if(y == 0){
				continue;
			}
			for(int j = maxLen - 1; j >= 0; j--){
				int x = maxStr[j] - '0';
				int a = x * y + flag;
				sum += a % 10 + '0';
				flag = a / 10;
			}
			if(flag){
				sum += flag + '0';
				flag = 0;
			}
			res.push_back(sum);
		}
		
		int resLen = res.size();
		string end;
		for(int i = 0; i < resLen; i++){
			reverse(res[i].begin(), res[i].end());
			end = addStrings(end, res[i]);
		}
		
		return end;
    }
	
	// 简化代码
	string addStrings(string num1, string num2) {
		int len1 = num1.size();
		int len2 = num2.size();
		int flag = 0;
		string sum;
		sum.reserve(len2 + 1);
		int i = len1 - 1;
		int j = len2 - 1;
		while(i >= 0 || j >= 0 || flag > 0){
			int x = i >= 0 ? num1[i--] - '0' : 0;
			int y = j >= 0 ? num2[j--] - '0' : 0;
			
			int tmp = x + y + flag;
			if(tmp >= 10){
				flag = 1;
				tmp = tmp - 10;
			}else{
                flag = 0;
            }
			sum += (tmp + '0');
		}
        reverse(sum.begin(), sum.end());
		return sum;
    }
};

int main(){
	Solution so;
	string s1 = "36";
	string s2 = "26";
	string s3 = so.multiply(s1, s2);
	cout << s3 << endl;
	return 0;
}